The present application is related to application of David A. Brown, David Stuart, and Stacy Nichols, filed on Dec. 5, 1997 and entitled xe2x80x9cLink List Block Allocation Method and Structure for Queuing Pointers in Memory,xe2x80x9dwhich is incorporated herein by reference.
The present invention relates to a multi-stage switch for transmitting electrical signals such as cells or packets.
FIG. 1 illustrates a conventional multi-stage switch. The switch includes first-stage multiplexers 100, each referred to as a switch fabric card (SFC), receiving a plurality of signals. A third stage includes demultiplexers 102. Between the first and third stages lies a second stage, including switches 101. Switches 101 control the transmission of signals from the first stage to the third stage. After the first stage receives signals, the second stage queues and sends them to a particular one of the third-stage demultiplexers. Thus, the second-stage switches route incoming signals from the first stage to a particular one of the third stages.
In certain multi-stage switches, the second-stage switches may experience a xe2x80x9cbottleneckxe2x80x9d if too many signals pass through a particular one of the second-stage switches. Designing such switches therefore involves determining how to distribute the signals from the first stage among the switches in the second stage. When multi-stage switch systems transmit too many signals through one of the second-stage switches, those systems do not use all switches in the second stage most efficiently. As a result, system performance degrades.
In addition, multi-stage switches must perform processing to track the signals, which slows their performance. Also, certain applications require maintaining the incoming signals in the same order, which also involves processing that can decrease the speed of the switch.
A multi-stage switch consistent with the present invention includes a plurality of output circuits, a plurality of input circuits containing cells destined for at least one of the output circuits, a plurality of switches for receiving the cells from a particular one of the input circuits and transmitting the cells to a particular one of the output circuits, and a scheduler circuit for transferring cells from an input circuit to an output circuit in the same temporal ordering, and distributes cells evenly across the middle stages to eliminate bottlenecks. A method consistent with the present invention transmits cells through a multi-stage switch. The method comprises queuing a plurality of cells in a plurality of input circuits, each of the cells being destined for at least one of a plurality of output circuits, and transmitting the cells, through a plurality of switches, from the one of the input circuits containing that cell to the ones of the output circuits for which the cell is destined by routing the cells in essentially the same temporal order as the cells are transmitted from the input circuits to the switches.